/*
 * Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.
 */
package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Sudoku {
    public void solveSudoku(char[][] board) {
        // Start typing your Java solution below
        // DO NOT write main() function
        solve(board, 0, 0);
    }
    
    public boolean solve(char[][] board, int r, int c)
    {
        while(board[r][c] != '.')
        {
            if(r == 8 && c == 8)
                break;
            r = (c == 8) ? r+1 : r;
            c = (c == 8) ? 0 : c+1;
        }
        if(board[r][c] != '.')
            return true;
        
        List<Character> pos = getPos(board, r, c);
        for(int i = 0; i < pos.size(); i++)
        {
            board[r][c] = pos.get(i);
            if(solve(board, r, c))
                return true;
            board[r][c] = '.';
        }
        return false;
    }
    
    public List<Character> getPos(char[][] board, int r, int c)
    {
        List<Character> pos = new ArrayList<Character>();
        Set<Character> found = new HashSet<Character>();
        int sr = r/3*3;
        int sc = c/3*3;
        for(int i = 0; i < 9; i++)
        {
            found.add(board[i][c]);
            found.add(board[r][i]);
            found.add(board[sr+i/3][sc+i%3]);
        }
        for(int i = 0; i < 9; i++)
        {
            if(!found.contains((char)(i + '1')))
                pos.add((char)(i + '1'));
        }
        return pos;
    }
}
